Decision trees [3, 4, 8, 31, 34, 40] and systems of decision rules [6, 7, 11, 14, 33, 34, 35, 36] are widely used as classifiers, knowledge representation tools, and algorithms. They are known for their interpretability in data analysis [10, 15, 23, 41]. Investigating the relationship between these two models is an important task in computer science. Converting decision trees into decision rule systems is a well-known and simple process [37, 38, 39]. This paper focuses on the inverse transformation problem, which is not trivial. The research related to this problem encompasses several directions: Two-stage construction of decision trees. This approach involves building decision rules based on input data, followed by the construction of decision trees or decision structures (which are generalizations of decision trees) using the generated rules. The benefits of this two-stage construction method are explained in [1, 2, 17, 18, 19, 20, 21, 22, 42].

In this paper, we consider the problems of transforming systems of decision rules into decision trees. This paper builds upon our previous work [12]. In that paper, we showed that the minimum depth of a decision tree derived from the decision rule system can be much less than the number of different attributes in the rules from the system. In such cases, it is reasonable to use decision trees. In the present paper, for some types of decision rule systems and problems, we prove the existence of polynomial time algorithms for the construction of decision trees and two types of acyclic decision graphs representing decision trees. In all other cases, we prove the absence of such algorithms using the fact that the minimum number of nodes in decision trees or acyclic decision graphs can grow as a superpolynomial function depending on the size of decision rule systems. To avoid difficulties related to the number of nodes in the decision trees, we discuss also the possibility of not building the entire decision tree, but describing the computation path in this tree for the given input.